package com.atguigu.day02;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// 邻接表来表示图数据结构
// HashMap的用法
// 拓扑排序算法
public class Example1 {
    public static void main(String[] args) {
        // HashMap<顶点，指向的所有顶点组成的列表>
        var dag = new HashMap<String, List<String>>();

        // 添加A -> B, A -> C
        var APointTo = new ArrayList<String>();
        APointTo.add("B");
        APointTo.add("C");
        dag.put("A", APointTo);

        // B -> D, B -> E
        var BPointTo = new ArrayList<String>();
        BPointTo.add("D");
        BPointTo.add("E");
        BPointTo.add("C");
        dag.put("B", BPointTo);

        // C -> D, C -> E
        var CPointTo = new ArrayList<String>();
        CPointTo.add("D");
        CPointTo.add("E");
        dag.put("C", CPointTo);

        // 找出从起点到终点的所有路线
        // 拓扑排序
        // 参数列表：有向无环图，当前遍历的顶点，已经遍历过的路径
        topologicalSort(dag, "A", "A");
    }

    public static void topologicalSort(Map<String, List<String>> dag, String currentVertex, String path) {
        // 如果当前遍历的顶点是终点，那么直接输出路径
        if (dag.get(currentVertex) == null) {
            System.out.println(path);
        } else {
            // 遍历当前顶点指向的所有顶点
            for (var nextVertex : dag.get(currentVertex)) {
                topologicalSort(dag, nextVertex, path + " --> " + nextVertex);
            }
        }
    }
}
